package io.tec.cloud.algorithm.c14;

import java.util.PriorityQueue;

/**
 * 80	14_2	14	2	14贪心算法（下）	金条分割的最小代价
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。
 * 比如长度为20的金条，不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?
 * <p>
 * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
 * <p>
 * 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50;一共花费110铜板。
 * 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30;一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 */
public class Code20220728_14_2 {

    public static void main(String[] args) {
        int[] arr = {7, 8, 10, 12, 15, 16, 23, 24};
        System.out.println(lessMoney2(arr));
    }

    public static int lessMoney2(int[] arr) {
        PriorityQueue<Integer> heap = new PriorityQueue();

        for (int item : arr) {
            heap.add(item);
        }
        int cost = 0;
        while (heap.size() > 1) {
            int item = heap.poll() + heap.poll();
            System.out.println(item);
            heap.add(item);
            cost += item;
        }
        return cost;
    }
}
